Hledani v netridenem poli
Otázka od: Pavel Poles
16. 4. 2004 15:14
Zdravim konferenci,
mam array of integer naplnene hodnotami ale nesetridene,
v tomto poli potrebuji najit index zadaneho cisla.
Jakym nejrychlejsim zpusobem by slo toto provest?
Napada mne nekolik zpusobu:
1) Sekvencne
2) Vytvorit dvourozmerne pole, prvni sloupec puvodni hodnoty,
druhy sloupec indexi v puvodnim poli, setridit podle prvniho sloupce
a najit hodnotu pulenim intervalu - druhy sloupec vrati index v puvodnim
poli
3) Pole nacpat do HashedStringList a v tom vyhledavat, to ale asi nebude
nejrychlejsi kvuli konverzi IntToStr...
Predem dekuji za napady
Pavel Poles
Odpovedá: Daniel Frantik
16. 4. 2004 15:14
To zavisi na tom, kolikrat budes v jiz setridenem seznamu hledat nejake
cislo... Trideni ma slozitost minimalne n*log(n), zatimco sekvencni
pruchud n .... Takze musis hledat alespon log(n) krat aby melo smysl
trideni... U hashovani zase roste rezie -> mimoto porovnani hashe bude
pomalejsi nez porovnani integeru...
Tedy ja bych krome extremnich pripadu zustal u sekvencniho pruchodu ...
Danik
> -----Original Message-----
> From: delphi-l-owner@clexpert.cz
> mam array of integer naplnene hodnotami ale nesetridene,
> v tomto poli potrebuji najit index zadaneho cisla.
> Jakym nejrychlejsim zpusobem by slo toto provest?
Odpovedá: delphin@post.cz
16. 4. 2004 15:14
> mam array of integer naplnene hodnotami ale nesetridene,
> v tomto poli potrebuji najit index zadaneho cisla.
> Jakym nejrychlejsim zpusobem by slo toto provest?
Pokud se jedna o jednorazovou akci, tak nejrychlejsi bude je sekvencne
projit. Na tohle existuje specializovana asm instrukce SCASD s jejiz
pouzitim to bude nejrychlejsi.
Pokud by se vyhledavalo opakovane, tak stoji za uvahu pole predem setridit a
vyhledavat binarne.
Odpovedá: Dalibor Toman
16. 4. 2004 16:54
On Friday, April 16, 2004 3:17 PM [CET], Daniel Frantik
<frantik@telpro.cz> wrote:
> To zavisi na tom, kolikrat budes v jiz setridenem seznamu hledat
> nejake cislo... Trideni ma slozitost minimalne n*log(n), zatimco
> sekvencni pruchud n .... Takze musis hledat alespon log(n) krat aby
> melo smysl trideni... U hashovani zase roste rezie -> mimoto
> porovnani hashe bude pomalejsi nez porovnani integeru...
> Tedy ja bych krome extremnich pripadu zustal u sekvencniho pruchodu
k tomu hashovani - samozrejme je nesmysl vyrabet stringovy hash.
Nabizi se vyrobit hash o delce 8 ci 16 bitu (napriklad jen poscitat
jednotlive wordy - konkretni reseni zalezi na rozlozeni hodnot tech
32bit cisel v poli). Ovsem znamenalo by to prevest vstupni pole do
vice mensich 'policek' (pole - resp spojovy seznam cisel se stejnym
hasem) - cili uplne zmenit usporadani dat. Pokud napriklad to vstupni
pole stejne program od nekud nacita, pak muze misto nej rovnou
vytvorit hashovaci pole s odkazy do mensich 'policek'.
Vhodnost ci nevhodnost tohoto reseni samozrejme zavisi na konkretnich
potrebach programu atd
D. Toman
Odpovedá: Daniel Frantik
19. 4. 2004 15:15
> -----Original Message-----
> k tomu hashovani - samozrejme je nesmysl vyrabet stringovy
> hash. Nabizi se vyrobit hash o delce 8 ci 16 bitu (napriklad
A porovnani jednoho 8-bit/16-bit bude rychlejsi nez porovnani 32 bit na
32-bit procesoru? - to tezko, ne?
Danik
Odpovedá: delphin@post.cz
19. 4. 2004 15:43
> A porovnani jednoho 8-bit/16-bit bude rychlejsi nez porovnani 32 bit na
> 32-bit procesoru? - to tezko, ne?
Porovnani 8,16 a 32 bitovych cisel trva stejne dlouho, ale v dnesni dobe,
kdy rychlost pameti pokulhava za CPU bude od jisteho poctu cisel viditelny
rozdil mezi nactenim 25%, 50% a 100% dat.
Odpovedá: Dalibor Toman
19. 4. 2004 15:56
----- Original Message -----
From: "Daniel Frantik" <frantik@telpro.cz>
To: <delphi-l@clexpert.cz>
Sent: Monday, April 19, 2004 4:11 PM
Subject: Re: Hledani v netridenem poli
> > -----Original Message-----
> > k tomu hashovani - samozrejme je nesmysl vyrabet stringovy
> > hash. Nabizi se vyrobit hash o delce 8 ci 16 bitu (napriklad
>
> A porovnani jednoho 8-bit/16-bit bude rychlejsi nez porovnani 32 bit
na
> 32-bit procesoru? - to tezko, ne?
ja to snad nekde tvrdil?
ale v tomto pripade se nabizi vyrobit jedno mensi pole (mensi nez 2^32
radku - tedy napriklad 2^8 ci 2^16) a vypocteny hash pouzit primo jako
index do pole. Cili velice rychle jsem schopen omezit mnozinu
prohledavanych integeru (pocet komparaci) jen na ty, ktere maji
konkretni stejny hash. Pri vhodnem rozlozeni cisel a navrhu vypoctu
hashe je vysledkem razantni zkraceni doby prohledavani.
Kapisto?
D. Toman